import java.lang.System;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 合并有重叠的区间
 *
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class MergeInterval {

    public List<Interval> solution(List<Interval> intervals) {

        if (intervals == null || intervals.size() == 0) {
            return intervals;
        }

        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        Interval ii, jj;
         
        for (int i = 0; i < intervals.size(); i++) {
            ii = intervals.get(i);
            for (int j = i + 1; j < intervals.size(); j++) {
                jj = intervals.get(j);
                if (ii.end >= jj.start) {
                    ii.end = Math.max(jj.end, ii.end);
                    intervals.remove(j);
                    j --;
                }
            }
        }
        return intervals;
    }

    static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    public static void main(String[] args) {
        List<Interval> data = new ArrayList<>();
        data.add(new Interval(1,3));
        data.add(new Interval(2,6));
        data.add(new Interval(15,18));
        data.add(new Interval(8,10));
        List<Interval> result = new MergeInterval().solution(data);
        System.out.print("result: \n");
        for (Interval item: result){
            System.out.print("[" + item.start + "," + item.end + "]\n");
        }
    }
}

